#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int ret = 0;
    int zeroCount = 0;
    int row = 0, col = 0;
    int RowCh[4] = { 0,0,-1,1 };
    int ColCh[4] = { 1,-1,0,0 };
    int uniquePathsIII(vector<vector<int>>& grid) {
        row = grid.size();
        col = grid[0].size();
        int oneRow = 0;
        int oneCol = 0;
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                if (grid[i][j] == 0)
                    zeroCount++;
                if (grid[i][j] == 1)
                {
                    oneCol = j;
                    oneRow = i;
                }
            }
        }

        dfs(grid, oneRow, oneCol, -1);

        return ret;
    }

    void dfs(vector<vector<int>>& grid, int i, int j, int count)
    {
        if (i < 0 || i == row || j < 0 || j == col || grid[i][j] == -1)
            return;

        if (grid[i][j] == 2 && count == zeroCount)
        {
            ret++;
            return;
        }

        int tmp = grid[i][j];
        grid[i][j] = -1;
        for (int k = 0; k < 4; ++k)
        {
            dfs(grid, i + RowCh[k], j + ColCh[k], count + 1);
        }
        grid[i][j] = tmp;
    }
};